home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 18326 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.8 KB
  1. Path: ix.netcom.com!news
  2. From: Bradd W. Szonye <bradds@ix.netcom.com>
  3. Newsgroups: comp.lang.c++
  4. Subject: RE: Special sort algorithm
  5. Date: 19 Apr 1996 09:28:01 GMT
  6. Organization: Netcom
  7. Message-ID: <01bb2dd2.cb714200$c6c2b7c7@Zany.localhost>
  8. References: <31593E09.29A0@kmd.dk> <4jciq9$1d0@news.microsoft.com>
  9. NNTP-Posting-Host: det-mi6-06.ix.netcom.com
  10. X-NETCOM-Date: Fri Apr 19  4:28:01 AM CDT 1996
  11. X-Newsreader: Microsoft Internet News
  12.  
  13.  
  14. On Wednesday, March 27, 1996, Dann Corbit wrote...
  15. > In article <31593E09.29A0@kmd.dk>, cab@kmd.dk says...
  16. > >
  17. > >Hi
  18. > >
  19. > >This is not strictly related to C++, but I guess some of you may have a
  20. hint
  21. > >on this anyway.
  22. > >
  23. > >I am trying to make a DOS file sorting program, which is to be part of
  24. a commercial product.
  25. > >It must :
  26. > > - Sort big files of short lines
  27. > >   lines are uneven length
  28. > >   files are XX MB
  29. > >   lines are < 100 chars
  30. > > - Put resulting file in original file
  31. > > - Run in very little memory ( < 50 K)
  32. > > - Use about no extra disk space ( < 10% extra)
  33. > > - Run reasonably fast
  34. > >
  35. > >I have tried implementing in-file bubblesort and others with the
  36. language
  37. > >being C++. But they are way too slow, even with some optimizing
  38. buffers.
  39. > >
  40. > Order of preference:
  41. >     counting sort, singleton's sort (ACM 347), heapsort.
  42. > definitely not bubblesort.  It is one of the worst.
  43. > 
  44. > You will have to run a merge phase, since your in-memory requirements
  45. > are so small.
  46.  
  47. If you want a good introduction to external sorting, pick up Robert
  48. Sedgewick's "Algorithms," "Algorithms in C," or "Algorithms in C++,"
  49. according to your preference.
  50.  
  51. If you want the definitive collection of searching and sorting methods,
  52. try to find Don Knuth's "Art of Computer Programming, Volume III:
  53. Searching and Sorting."
  54.  
  55. Both are expensive, and Knuth is difficult to read. But they're great
  56. resources.
  57.  
  58.  
  59.